import typing
from provate import TreeNode

# 题目：实现一个函数，用来判断一个二叉树是否是对称的，如果一个二叉树和它的镜像一样，那么它是对称的

def is_symmetrical(root:TreeNode)->bool:
    return is_symmetrical_core(root, root)

def is_symmetrical_core(root1:TreeNode, root2:TreeNode)->bool:
    if not root1 and not root2:
        return True

    if not root1 or not root2:
        return False

    if root1.value != root2.value:
        return False

    return is_symmetrical_core(root1.leftchild,root2.rightchild) and is_symmetrical_core(root1.rightchild, root2.leftchild)

if __name__ == '__main__':
    root1 = TreeNode(8)
    root1.leftchild = TreeNode(6)
    root1.leftchild.leftchild = TreeNode(5)
    root1.leftchild.rightchild = TreeNode(7)
    root1.rightchild = TreeNode(6)
    root1.rightchild.leftchild = TreeNode(7)
    root1.rightchild.rightchild = TreeNode(5)

    root2 = TreeNode(8)
    root2.leftchild = TreeNode(6)
    root2.leftchild.leftchild = TreeNode(5)
    root2.leftchild.rightchild = TreeNode(7)
    root2.rightchild = TreeNode(9)
    root2.rightchild.leftchild = TreeNode(7)
    root2.rightchild.rightchild = TreeNode(5)

    root3 = TreeNode(7)
    root3.leftchild = TreeNode(7)
    root3.leftchild.leftchild = TreeNode(7)
    root3.leftchild.rightchild = TreeNode(7)
    root3.rightchild = TreeNode(7)
    root3.rightchild.leftchild = TreeNode(7)

    print(is_symmetrical(root1))
    print(is_symmetrical(root2))
    print(is_symmetrical(root3))